Міністерство освіти і науки України
Національний університет “Львівська політехніка”
Кафедра прикладної математики
КУРСОВА РОБОТА
з курсу
“Дискретна математика”
на тему:
“Алгебра предикатів. Квантори.
Означення. Операції. ”
Зміст
Вступ
Поняття предиката
Логiка предикатiв
Квантори
Формули логіки предикатів
Рівносильність формул
Здійснюваність. Загальнозначущість.
Література
Анотація
Вступ
Алгебра висловлювань i як формальна (аксiоматична) теорiя, є важливою i невiд’ємною складовою частиною всiх числень математичної логiки. Однак вона є занадто бiдною для опису та аналiзу найпростiших логiчних міркувань.
Однiєю з причин цього є те, що у численнi висловлювань будь-яке просте висловлення розглядається як вихiдний об’єкт дослiдження, неподiльне цiле, позбавлене частин i внутрiшньої структури, яке має лише одну властивiсть - бути або iстинним, або хибним.
Для того, щоб побудувати систему правил, яка дозволяла б проводити логiчнi мiркування для виведення нетривiальних правильних висновкiв з урахуванням будови i змiсту простих висловлень, використовується формальна теорiя, що дiстала назву числення предикатiв.
Якщо числення висловлювань дає змогу доводити теореми для внутрішніх потреб логіки, то числення предикатів забезпечує можливість описувати й доводити теореми для конкретних розділів математики. Логіка предикатів дає змогу формулювати співвідношення між елементами реального світу і виводити подібні відношення або теореми в математиці. Числення висловлювань – досить вузька логічна система. Існують, наприклад, такі типи логічних міркувань, які не можуть бути здійснені в межах логіки висловлювань:
Кожний друг Івана є другом Петра. Сидір не є другом Івана. Отже, Сидір не є другом Петра.
Просте число два – парне. Отже існують прості парні числа.
Коректність цих висновків грунтується на внутрішній структурі самих речень і значень слів “кожний” та “існують”.
Існують такі види логічних формул, які не можна записати у вигляді формул числення висловлювань. Наприклад:
Всі риби, окрім акул, добре відносяться до дітей;
Всі люди смертні. Сократ – людина. Значить Сократ смертний.
Коректність таких висновків грунтується не тільки на істиності відповідних функціональних відношень, а також і на розумінні таких слів, як “всі”, “всякий” і т.д.
Для того щоб зробити більш зрозумілою структуру складних висловлювань, користуються спеціальною мовою – мовою числення предикатів першого порядку.
1.Поняття предиката
Теорiя предикатiв починається з аналiзу граматичної будови простих висловлювань i грунтується на такому висновку: простi висловлювання виражають той факт, що деякi об’єкти (або окремий об’єкт) мають певнi властивостi, або що цi об’єкти знаходяться мiж собою у певному вiдношеннi.
Наприклад, в iстинному висловлюванні «3 є просте число» пiдмет «3» - це об’єкт, а присудок «є просте число» виражає деяку його властивiсть.
У латинськiй граматицi присудок називається предикатом, звiдси цей термiн i увiйшов у математичну логiку. Головним для логiки предикатiв є саме друга складова речення-висловлення - присудок-властивiсть. Вона фiксується, а значення об’єкта пропонується змiнювати так, щоб кожен раз отримувати осмисленi речення, тобто висловлення.
Розглянемо речення, що залежить від параметрів, наприклад «х – парне число», «х менше у», «х + у = z», «х – батько у», «х та у – брати» тощо. Якщо х, у, z у перших трьох реченнях замінити деякими числами, то матимемо певні висловлення, які можуть бути істинними або хибними. Наприклад, «3 – парне число», «2 менше 5», «3 + 2 = 7». Останні два речення виражають родинні відносини між членами сім’ї і перетворюються на певні висловлення, істинні або хибні, при заміні х та у іменами членів сім’ї: «Іван – батько Петра», «Іван і Олег брати».
Речення такого типу називаються предикатами. Точніше предикатом Р(х1,...,хn) називається функція, змінні якої набувають значень із деякої множини М, а сама вона набуває двох значень: 1 (істинне) і 0 (хибне), тобто Р(х1,...,хn): Мn → {1, 0}.
Множина M називається предметною о...